1. Field of the Invention
The present invention is directed to error correcting systems which utilize an error correcting code to correct errors which have occurred in the transmission or storage of information. The present invention provides a method and apparatus for determining the log of an element in the Galois Field GF(2.sup.m). More particularly, the present invention is directed to a method and apparatus for determining the log of an element in GF(2.sup.m) with the help of a small table of selectable size which applies for any GF(2.sup.m) and any value of m.
2. Related art
In Galois Field GF(2.sup.m), elements are primarily represented in two different forms: vector form and power form. In vector form, each element of the Galois Field is represented by a polynomial of degree m-1 or less which has coefficients from the binary field (i.e., 0 or 1). In power form, all elements of the Galois Field (except the zero element) are represented by powers of a primitive element of the Field.
For purposes of convenience and high speed processing, elements in GF(2.sup.m) are generally represented in vector form. All operations such as addition, multiplication, division, etc., are performed in vector form using special purpose hardware.
When performing error detection and correction, and more particularly during the associated decoding process, after error location numbers are obtained in vector form, it is necessary to find the log of the error location vector in order to determine the error location within the length of the codeword containing the error. To illustrate, if a is a primitive element in GF(2.sup.m), and if a.sup.k represents an error location vector, then: EQU a.sup.k =a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.0 EQU and EQU log[a.sup.k ]=log[a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.0 ]=k
where k represents the location of an error in the codeword.
In order to provide for on-the-fly (i.e., in real-time) error correction, the prior art teaches that a log table must be implemented on an integrated circuit chip. This is true even if the chip is provided with special purpose fast multipliers and inverters. Such a table requires a ROM table of size 2.sup.m * m, which can be quite expensive for large values of m.
Therefore, it would be desirable to provide an alternative method and apparatus for determining the log of an element in GF(2.sup.m) that provides for on-the-fly error correction and is inexpensive to implement.